package com.xmg.dataStructure.tree.huffmanTree;

import java.io.*;
import java.util.*;

public class HuffmanCode {
    public static void main(String[] args) {
//        String str = "i like like like java do you like a java";
//        byte[] bytes = str.getBytes();
//        System.out.println("原始长度："+bytes.length +"  内容："+Arrays.toString(bytes));
//
//        byte[] huffmanZip = huffmanZip(bytes);
//        System.out.println("压缩后的长度："+huffmanZip.length+" 内容："+Arrays.toString(huffmanZip));
//
//        byte[] source = decode(huffmanCodes, huffmanZip);
//        System.out.println("解码后的字符串："+new String(source));
        /*
        List<CNode> nodes = getNodes(bytes);
        System.out.println("赫夫曼树 notes = "+nodes);

        CNode root = createHuffmanTree(nodes);
//        preOrder(root);

        //生成赫夫曼编码
        getCodes(root);
        System.out.println("生成的赫夫曼编码："+huffmanCodes);

        //进行压缩
        byte[] zip = zip(bytes, huffmanCodes);
        System.out.println("编码后的byte数组："+Arrays.toString(zip));
         */

        String src = "g://123.bmp";
        String dst = "g://dst.zip";
//        zipFile(src,dst);

        unZipFile(dst,src);
    }

    /**
     * 对压缩文件进行解压
     * @param zipFile 压缩文件
     * @param dstFile 解压后文件
     */
    public static void unZipFile(String zipFile,String dstFile){
        InputStream inputStream = null;
        ObjectInputStream objectInputStream = null;
        OutputStream outputStream = null;
        try {
            inputStream = new FileInputStream(zipFile);
            objectInputStream = new ObjectInputStream(inputStream);
            byte[] huffmanBytes = (byte[]) objectInputStream.readObject();
            huffmanCodes = (Map<Byte, String>) objectInputStream.readObject();
            byte[] decode = decode(huffmanCodes, huffmanBytes);

            outputStream = new FileOutputStream(dstFile);
            outputStream.write(decode);
        }catch (Exception e){

        }finally {
            try {
                objectInputStream.close();
                inputStream.close();
                outputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }

        }
    }

    /**
     * 压缩文件
     * @param srcFile 源文件路径
     * @param dstFile 压缩后文件路径
     */
    public static void zipFile(String srcFile,String dstFile){
        FileInputStream inputStream = null;
        FileOutputStream outputStream = null;
        ObjectOutputStream objectOutputStream = null;
        try {
            inputStream = new FileInputStream(srcFile);
            byte[] inFile = new byte[inputStream.available()];
            inputStream.read(inFile);
            //进行压缩
            byte[] outFile = huffmanZip(inFile);

            outputStream = new FileOutputStream(dstFile);
            objectOutputStream = new ObjectOutputStream(outputStream);
            objectOutputStream.writeObject(outFile);
            //此处还需要将赫夫曼编码写入压缩文件，恢复源文件时使用
            objectOutputStream.writeObject(huffmanCodes);

        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            try {
                inputStream.close();
                objectOutputStream.close();
                outputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    /**
     *完成对压缩数据的解码
     * @param huffmanCodes 赫夫曼编码表
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return  原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length;i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i==huffmanBytes.length-1);
            stringBuilder.append(byteToBitString(!flag,b));//此处只有最后一个字节没有补位，其他字节都为true进行补位，负数按位或之后还是原来数据
        }
//        System.out.println(stringBuilder);
        Map<String,Byte> map = new HashMap<>();
        for(Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }
        //创建集合，存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag){
                String str = stringBuilder.substring(i,i+count);
                if(map.containsKey(str)){
                    b= map.get(str);
                    flag = false;
                }else {
                    count++;
                }
            }
            list.add(b);
            i += count;
        }
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }

    /**
     * 将一个byte转换成二进制的字符串 返回的是补码
     * @param flag 标识是否需要补高位 true需要补高位 false不补
     * @param b 待转换byte
     * @return 按补码返回的二进制对应的字符串
     */
    private static String byteToBitString(boolean flag,byte b){
        int temp = b;
        if(flag) {
            temp |= 256; //按位或  补齐8位
        }
        String str = Integer.toBinaryString(temp);
        if(str.length()>8){
            return str.substring(str.length()-8);
        }else{
            return str;
        }

    }

    //压缩方法封装
    private static byte[] huffmanZip(byte[] bytes){
        List<CNode> nodes = getNodes(bytes);
        CNode root = createHuffmanTree(nodes);
        //生成赫夫曼编码
        getCodes(root);
        //进行压缩
        byte[] zip = zip(bytes, huffmanCodes);
        return zip;
    }

    //编写方法，将字符串对应的byte[]数组，返回赫夫曼编码表处理后的byte[]
    /**
     *
     * @param bytes 原始字符串对应的byte[]
     * @param huffmanCodes 赫夫曼编码表
     * @return 返回赫夫曼编码表处理之后的byte[]
     */
    private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
        //1、利用huffmanCodes 将 bytes 转成编码后的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes
        for (byte aByte : bytes) {
            stringBuilder.append(huffmanCodes.get(aByte));
        }
        //System.out.println("赫夫曼编码后的string："+stringBuilder.toString());
        //将字符串转换为byte[]
        int len; //一句话完成  len = (stringBuilder + 7) / 8;
        if(stringBuilder.length()%8==0){
            len = stringBuilder.length()/8;
        }else{
            len = stringBuilder.length()/8 + 1;
        }
        //创建一个存储压缩后的byte数组
        byte[] huffmanBytes = new byte[len];
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte ;
            if(i+8>stringBuilder.length()){
                strByte = stringBuilder.substring(i);
            }else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            huffmanBytes[i/8] = (byte)Integer.parseInt(strByte,2);
        }

        return huffmanBytes;
    }

    //生成赫夫曼树对应的赫夫曼编码
    //1、编码表放在Map中
    //2、生成赫夫曼编码表的时候需要拼接路径 StringBuilder，存储叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();
    static Map<Byte,String> huffmanCodes = new HashMap<>();

    private static void getCodes(CNode node){
        if(node==null){
            return;
        }
        getCodes(node,"",stringBuilder);
    }
    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到，放入到huffmanCodes中
     * @param node 传入节点
     * @param code 路径 左节点0 右节点1
     * @param stringBuilder 用户拼接路径
     */
    private static void getCodes(CNode node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if(node!=null){
            if(node.data==null){//非叶子节点  继续递归
                getCodes(node.left,"0",stringBuilder2);
                getCodes(node.right,"1",stringBuilder2);
            }else{
                //叶子节点
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }

    }

    /**
     *
     * @param bytes 接收字节数组
     * @return  返回Node格式的list
     */
    private static List<CNode> getNodes(byte[] bytes){
        List<CNode> nodes = new ArrayList<>();
        Map<Byte,Integer> counts = new HashMap<>();
        for (byte aByte : bytes) {
            Integer count = counts.get(aByte);
            if(count==null){
                counts.put(aByte,1);
            }else{
                counts.put(aByte,count+1);
            }
        }
        for (Map.Entry<Byte,Integer> entry:counts.entrySet()){
            nodes.add(new CNode(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    private static CNode createHuffmanTree(List<CNode> nodes){

        while (nodes.size()>1){
            Collections.sort(nodes);
            CNode left = nodes.get(0);
            CNode right = nodes.get(1);
            CNode parent = new CNode(null,left.weight+right.weight);
            parent.left = left;
            parent.right = right;
            nodes.add(parent);
            nodes.remove(left);
            nodes.remove(right);
        }
        return nodes.get(0);
    }

    public static void preOrder(CNode node){
        if(node==null){
            System.out.println("空的");
        }else{
            node.preOrder();
        }
    }
}

class CNode implements Comparable<CNode>{
    Byte data;  //数据本身
    int weight; //权值

    CNode left;
    CNode right;

    public CNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(CNode o) {
        //从小到大排序
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "CNode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preOrder(){
        System.out.println(this);
        if(this.left!=null) {
            this.left.preOrder();
        }
        if(this.right!=null) {
            this.right.preOrder();
        }
    }
}